package leetcode.year2021.month10;

//152. 乘积最大子数组
public class _31_01MaxProduct152 {
  public int maxProduct(int[] nums) {
    /**
     * 动态规划，需要找出动态转移方程
     */
    int[] dpMax = new int[nums.length];
    int[] dpMin = new int[nums.length];

    int ans = nums[0];

    dpMax[0] = nums[0];
    dpMin[0] = nums[0];

    for (int i = 1; i < nums.length; i++) {
      dpMax[i] = Math.max(dpMax[i-1] * nums[i], Math.max(dpMin[i-1] * nums[i],nums[i]));
      dpMin[i] = Math.min(dpMax[i-1] * nums[i], Math.min(dpMin[i-1] * nums[i],nums[i]));
      ans = Math.max(ans,dpMax[i]);
    }

    return ans;
  }

  /**
   * 152. 乘积最大子数组
   * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
   *
   *
   *
   * 示例 1:
   *
   * 输入: [2,3,-2,4]
   * 输出: 6
   * 解释: 子数组 [2,3] 有最大乘积 6。
   * 示例 2:
   *
   * 输入: [-2,0,-1]
   * 输出: 0
   * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
   */
}
